package com.shawn.datastructure.array;

/**
 * 实现一个支持动态扩容的数组
 */
public class MyArrayList<T> {

	/**
	 * 内置数组
	 */
	private T[] data;

	/**
	 * 容量
	 */
	private int capacity;

	/**
	 * 数组实际大小
	 */
	private int size;

	/**
	 * 默认数组大小
	 */
	private int DEFAUL_CAPACITY = 10;

	public MyArrayList() {
		data = (T[]) new Object[DEFAUL_CAPACITY];
		this.capacity = DEFAUL_CAPACITY;
	}

	public MyArrayList(int capacity) {
		data = (T[]) new Object[capacity];
		this.capacity = capacity;
	}

	public void add(int index, T value) {
		// 检查index
		checkIndexForAdd(index);
		// 判断容量是否已满
		if (data.length == size) {
			// 扩容
			resize();
		}
		// 数据搬移
		System.arraycopy(data, index, data, index + 1, size - index);
		data[index] = value;
		size++;
	}

	public void add(T value) {
		add(size, value);
	}

	public void addFirst(T value) {
		add(0, value);
	}

	public T remove(int index) {
		// 检查index
		checkIndex(index);
		T value = data[index];
		if ((size - index - 1) > 0) {
			System.arraycopy(data, index + 1, data, index, size - index - 1);
		}
		data[--size] = null;
		return value;
	}

	public T removeByElement(T t) {
		if (t == null) {
			for (int i = 0; i < size; i++) {
				T item = data[i];
				if (item == null) {
					return remove(i);
				}
			}
		} else {
			for (int i = 0; i < size; i++) {
				T item = data[i];
				if (item.equals(t)) {
					return remove(i);
				}
			}
		}
		return null;
	}

	public T removeLast() {
		return remove(size - 1);
	}

	public T removeFirst() {
		return remove(0);
	}

	public void set(int index, T value) {
		checkIndex(index);
		data[index] = value;
	}

	public T get(int index) {
		checkIndex(index);
		return data[index];
	}

	public T getByElement(T e) {
		if (e == null) {
			for (int i = 0; i < size; i++) {
				T item = data[i];
				if (item == null) {
					return get(i);
				}
			}
		} else {
			for (int i = 0; i < size; i++) {
				T item = data[i];
				if (item.equals(e)) {
					return get(i);
				}
			}
		}

		return null;
	}

	public int size() {
		return size;
	}

	public void print() {
		for (int i = 0; i < size; i++) {
			System.out.print(data[i]);
			if (i != size - 1) {
				System.out.print(", ");
			}
		}
		System.out.println();
	}

	private void resize() {
		int oldCapacity = data.length;
		int newCapacity = oldCapacity + (oldCapacity >> 1);
		if (newCapacity > Integer.MAX_VALUE - 8) {
			newCapacity = Integer.MAX_VALUE - 8;
		}
		T[] newData = (T[]) new Object[newCapacity];
		System.arraycopy(data, 0, newData, 0, size);
		data = newData;
	}

	private void checkIndexForAdd(int index) {
		if (index < 0 || index > size) {
			throw new IndexOutOfBoundsException("index is error: " + index);
		}
	}

	private void checkIndex(int index) {
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException("index is error: " + index);
		}
	}

	public static void main(String[] args) {
		MyArrayList<Integer> list = new MyArrayList<>(5);
		list.add(1);
		list.add(2);
		list.add(0, 3);
		list.add(3, 3);
		list.print();
		list.remove(3);
		list.print();
		list.add(4);
		list.print();
		list.remove(0);
		list.print();
		list.add(5);
		list.print();
		list.add(5);
		list.add(5);
		list.add(5);
		list.add(5);
		list.add(5);
		list.add(5);
		list.print();
		list.removeLast();
		list.print();
	}
}
